package com.cd.algorithm.order.code;

import java.util.Arrays;

/**
 * 归并排序
 * 遍历数组，将数组分成两半，分别对这两半进行排序，然后再将排序好的两半合并成一个数组。
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 *
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
        System.out.println("Before sorting:"+ Arrays.toString(arr));

        // sort the array using merge sort
        mergeSort(arr, 0, arr.length - 1);

        System.out.println("After sorting:"+ Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;

            // sort first and second halves
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);

            // merge the sorted halves
            merge(arr, low, mid, high);
        }
    }

    public static void merge(int[] arr, int low, int mid, int high) {
        int n1 = mid - low + 1;
        int n2 = high - mid;

        // create temp arrays
        int[] L = new int[n1];
        int[] R = new int[n2];

        // copy data to temp arrays L[] and R[]
        for (int i = 0; i < n1; i++) {
            L[i] = arr[low + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // merge the temp arrays back into arr[low..high]
        int i = 0, j = 0, k = low;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // copy remaining elements of L[], if there are any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // copy remaining elements of R[], if there are any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }


}
